#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node, *LinkedList;

LinkedList createLinkedList(int howMany) {
    LinkedList head, curr, tmp;
    head = curr = tmp = NULL;

    int i = 0;

    for (; i < howMany; i++) {
        tmp = (Node*)calloc(1, sizeof(Node));

        // 初始化为0， 表示这里还没有实际数据，可理解为空位
        // 这句不写其实也行，因为用的是calloc()申请内存, 此函数会自动将内存置0
        tmp->data = 0;

        if (!head) {
            head = tmp;
        } else {
            curr->next = tmp;
        }
        curr = tmp;
    }
    curr->next = head; // 最后一个节点指向第一个节点， 单循环链表
    return head;
}

int destroyLinkedList(LinkedList* list) {
    if (!list) {
        return 0;
    }

    LinkedList curr, next;

    curr = *list;
    next = NULL;

    while (next != *list) {
        next = curr->next;
        free(curr);
        curr = next;
    }
    *list = NULL;
    return 0;
}

int Magician(LinkedList head, int howMany) {
    LinkedList curr = head;
    curr->data = 1; // 第一张牌为1

    int count;
    int i, j;

    for (i = 2; i <= howMany; i++) {
        count = i;
        // 找出第i张牌的位置, 第i张牌距离第
        for (j = 0; j < count; j++) {
            curr = curr->next;
            if (curr->data != 0) { // 该位置已经有牌了
                // 这个节点就不能计数， 为了保证循环次数count不变
                // j--;
                count++;
            }
        }

        // 如果这个位置还没牌,
        // 在这里， 这个判断是没必要的
        // 因为上边的for循环一定会找到一个data不为0的位置，否则不会到这来
        // 为了逻辑清晰，还是写上
        if (curr->data == 0) {
            curr->data = i;
        }
    }

    return 0;
}

int main() {
    const int CARD_NUMBER = 13;
    LinkedList list = createLinkedList(CARD_NUMBER);
    Magician(list, CARD_NUMBER);

    LinkedList p = list;
    int i;

    // 1 8 2 5 10 3 12 11 9 4 7 6 13
    for (i = 0; i < CARD_NUMBER; i++, p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
    destroyLinkedList(&p);
    return 0;
}
